<?php
// This file is part of Preg question type - https://code.google.com/p/oasychev-moodle-plugins/
//
// Preg question type is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

/**
 * Functions to build nodes of regexp tree
 *
 * @package    qtype_preg
 * @copyright  2012 Oleg Sychev, Volgograd State Technical University
 * @author     Penskoy Nikita <nik95penik@yandex.ru>
 * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
 */

defined('MOODLE_INTERNAL') || die();

global $CFG;
require_once($CFG->dirroot . '/question/type/poasquestion/poasquestion_string.php');
require_once($CFG->dirroot . '/question/type/preg/preg_nodes.php');

function form_error($subtype, $addinfo, $addtonode = null) {
    // Create the error node itself.
    $error = new qtype_preg_node_error($subtype, htmlspecialchars($addinfo));
    $error->set_user_info(null, array(new qtype_preg_userinscription($addinfo)));

    // Add it to $addtonode if specified.
    if ($addtonode !== null) {
        $addtonode->errors[] = $error;
    }
    return $error;
}

/**
 * Returns a quantifier token.
 */
function form_quant($text, $infinite, $leftborder, $rightborder, $lazy, $greedy, $possessive) {
    $node = $infinite ? new qtype_preg_node_infinite_quant($leftborder, $lazy, $greedy, $possessive) : new
            qtype_preg_node_finite_quant($leftborder, $rightborder, $lazy, $greedy, $possessive);

    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));

    if (!$infinite && $leftborder > $rightborder) {
        $error = form_error(qtype_preg_node_error::SUBTYPE_INCORRECT_QUANT_RANGE, $leftborder . ', ' . $rightborder, $node);
        return $error;
    }
    return $node;
}

/**
 * Returns a named subexpression token.
 */
function form_named_subexpr($text, $name) {
    // Error: empty name.
    if ($name === '') {
        $error = form_error(qtype_preg_node_error::SUBTYPE_SUBEXPR_NAME_EXPECTED, $text);
            return $error;
    }

    return form_subexpr($text, qtype_preg_node_subexpr::SUBTYPE_SUBEXPR, -1, $name, false);
}

function form_subexpr($text, $subtype, $number = -1, $name = null, $isduplicate = false) {
    $node = new qtype_preg_node_subexpr($subtype, $number, $name, $isduplicate);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));
    return $node;
}

/**
 * Returns a conditional subexpression (number of name condition) token.
 */
function form_numeric_or_named_cond_subexpr($text, $number, $ending = '') {
    // Error: unclosed condition.
    if (qtype_preg_unicode::substr($text, core_text::strlen($text) - strlen($ending)) != $ending) {
        $error = form_error(qtype_preg_node_error::SUBTYPE_MISSING_CONDSUBEXPR_ENDING, $text);
        return $error;
    }

    $node = new qtype_preg_node_cond_subexpr(qtype_preg_node_cond_subexpr::SUBTYPE_SUBEXPR, $number);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));

    if (is_integer($number) && $number == 0) {
        // Error: reference to the whole expression.
        $error = form_error(qtype_preg_node_error::SUBTYPE_CONSUBEXPR_ZERO_CONDITION, $number, $node);
    } else if ($number === '') {
        // Error: assertion expected.
        $error = form_error(qtype_preg_node_error::SUBTYPE_CONDSUBEXPR_ASSERT_EXPECTED, $number, $node);
    }

    return $node;
}

/**
 * Returns a conditional subexpression (recursion condition) token.
 */
function form_recursive_cond_subexpr($text, $number) {
    // Error: unclosed condition.
    if (qtype_preg_unicode::substr($text, core_text::strlen($text) - 1) != ')') {
        $error = form_error(qtype_preg_node_error::SUBTYPE_MISSING_CONDSUBEXPR_ENDING, $text);
        return $error;
    }

    $node = new qtype_preg_node_cond_subexpr(qtype_preg_node_cond_subexpr::SUBTYPE_RECURSION, $number);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));

    if ($number === '') {
        // Error: assertion expected.
        $error = form_error(qtype_preg_node_error::SUBTYPE_CONDSUBEXPR_ASSERT_EXPECTED, $number, $node);
    }

    return $node;
}

/**
 * Returns a conditional subexpression (define condition) token.
 */
function form_define_cond_subexpr($text) {
    // Error: unclosed condition.
    if (qtype_preg_unicode::substr($text, core_text::strlen($text) - 1) != ')') {
        $error = form_error(qtype_preg_node_error::SUBTYPE_MISSING_CONDSUBEXPR_ENDING, $text);
        return $error;
    }

    $node = new qtype_preg_node_cond_subexpr(qtype_preg_node_cond_subexpr::SUBTYPE_DEFINE);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));

    return $node;
}

/**
 * Returns a named backreference token.
 */
function form_named_backref($text, $namestartpos, $opentype, $closetype) {
    // Error: missing opening characters.
    if (qtype_preg_unicode::substr($text, $namestartpos - 1, 1) !== $opentype) {
        $error = form_error(qtype_preg_node_error::SUBTYPE_MISSING_OPEN_PAREN, $opentype);
        return $error;
    }

    // Error: missing closing characters.
    if (qtype_preg_unicode::substr($text, core_text::strlen($text) - 1, 1) !== $closetype) {
        $error = form_error(qtype_preg_node_error::SUBTYPE_MISSING_BACKREF_ENDING, $closetype);
        return $error;
    }

    $name = qtype_preg_unicode::substr($text, $namestartpos, core_text::strlen($text) - $namestartpos - 1);

    // Error: empty name.
    if ($name === '') {
        $error = form_error(qtype_preg_node_error::SUBTYPE_SUBEXPR_NAME_EXPECTED, $text);
        return $error;
    }

    return form_backref($text, $name);
}

/**
 * Returns a backreference token.
 */
function form_backref($text, $number) {
    $node = new qtype_preg_leaf_backref($number);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));
    return $node;
}

/**
 * Returns a simple assertion token.
 */
function form_simple_assertion($text, $classname, $negative = false) {
    $node = new $classname($negative);
    $node->set_user_info(null, array(new qtype_preg_userinscription($text, $node->subtype)));
    return $node;
}

/**
 * Returns a character set token.
 */
function form_charset($text, $type, $data, $negative = false) {
    $node = new qtype_preg_leaf_charset();
    $uitype = $type === qtype_preg_charset_flag::TYPE_SET ? null : $data;
    $node->set_user_info(null, array(new qtype_preg_userinscription($text, $uitype)));
    $node->subtype = $type;

    if ($data !== null) {
        $flag = new qtype_preg_charset_flag;
        $flag->negative = $negative;
        if ($type == qtype_preg_charset_flag::TYPE_SET) {
            $data = new qtype_poasquestion_string($data);
        }
        $flag->set_data($type, $data);
        $node->flags = array(array($flag));
    }
    return $node;
}

/**
 * Returns a named subexpression call token.
 */
function form_named_subexpr_call($text, $name) {
    // Error: empty name.
    if ($name === '') {
        $error = form_error(qtype_preg_node_error::SUBTYPE_SUBEXPR_NAME_EXPECTED, $text);
        return $error;
    }
    return form_subexpr_call($text, $name);
}

/**
 * Returns a subexpression call token.
 */
function form_subexpr_call($text, $number) {
    $node = new qtype_preg_leaf_subexpr_call();
    $node->set_user_info(null, array(new qtype_preg_userinscription($text)));
    $node->number = $number;
    return $node;
}

function string_to_tokens($str) {
    $res = array();
    for ($i = 0; $i < qtype_preg_unicode::strlen($str); $i++) {
        $char = qtype_preg_unicode::substr($str, $i, 1);

        if ($char == ' ') {
            $char = '[ ]';
        } else if ($char == '$') {
            $char = '\$';
        } else if ($char == '^') {
            $char = '\^';
        } else if ($char == '.') {
            $char = '\.';
        } else if ($char == '+') {
            $char = '\+';
        } else if ($char == '[') {
            $char = '\[';
        } else if ($char == ']') {
            $char = '\]';
        } else if ($char == '|') {
            $char = '\|';
        } else if ($char == '?') {
            $char = '\?';
        } else if ($char == '*') {
            $char = '\*';
        } else if ($char == '{') {
            $char = '\{';
        } else if ($char == '}') {
            $char = '\}';
        } else if ($char == '\n') {
            $char = '\\n';
        }

        $res[] = form_charset($char, qtype_preg_charset_flag::TYPE_SET, $char);
    }
    return $res;
}

function convert_template($desc, &$pos = -1) {
    if ($pos == -1) {
        $desc = new qtype_poasquestion_string($desc);
        $pos = $desc->length() - 1;
    }

    $num = 0;
    $t = 0;

    while ($desc[$pos] == ' ') {
        // Пропустить пробелы
        $pos--;
    }
    while ($desc[$pos] >= '0' && $desc[$pos] <= '9') {
        // Считать количество детей
        $num += pow(10, $t) * ($desc[$pos]);
        $t++;
        $pos--;
    }

    $inquots = false;
    if ($desc[$pos] == '"') {
        // Посмотреть, в кавычках ли имя узла
        $inquots = true;
        $pos--;
    }

    $name = new qtype_poasquestion_string();
    $finish = false;
    while (!$finish && $pos >= 0) {
        // Считать имя до пробела или кавычек
        if ($desc[$pos] != ' ' && !$inquots || $inquots && ($desc[$pos] != '"' || $pos > 0 && $desc[$pos - 1] == '\\')) {
            $name->set_String($desc[$pos].$name->string());
            $pos--;
        } else {
            if ($desc[$pos] == '"') {
                $pos--;
            }
            $finish = true;
        }

    }

    if ($name->string() == '') {
        return null;
    }

    $ch = array();
    for ($i = 0; $i < $num && $pos > 0; $i++) {
        // Для всех детей
        $ch[] = convert_template($desc, $pos); // Запустить функцию рекурсивно
    }
    $ch = array_reverse($ch);

    if ($name == ".") {
        $node = new qtype_preg_node_concat();
        foreach ($ch as $child) {
            $node->operands[] = $child;
        }
    } else if ($name == '|') {
        $node = new qtype_preg_node_alt();
        foreach ($ch as $child) {
            $node->operands[] = $child;
        }
    } else if ($name == '\b') {
        $node = new qtype_preg_leaf_assert_esc_b(false);
    } else if ($name == '\B') {
        $node = new qtype_preg_leaf_assert_esc_b(true);
    } else if ($name == '^') {
        $node = new qtype_preg_leaf_assert_circumflex();
    } else if ($name == '$') {
        $node = new qtype_preg_leaf_assert_dollar();
    } else if (core_text::substr($name, 0, 3) == '\k<') {
        $node = form_named_backref($name, 3, '<', '>');
    } else if (core_text::substr($name, 0, 4) == '(?P<') {
        $node = form_named_subexpr('', core_text::substr($name, 4, -2));
        $node->operands[] = $ch[0];
    } else if ($name == '?') {
        $node = form_quant('?', false, 0, 1, false, true, false);
        $node->operands[] = $ch[0];
    } else if ($name == '??') {
        $node = form_quant('??', false, 0, 1, true, false, false);
        $node->operands[] = $ch[0];
    } else if ($name == '+') {
        $node = form_quant('+', true, 1, -1, false, true, false);
        $node->operands[] = $ch[0];
    } else if ($name == '+?') {
        $node = form_quant('+?', true, 1, -1, true, false, false);
        $node->operands[] = $ch[0];
    } else if ($name == '*') {
        $node = form_quant('*', true, 0, -1, false, true, false);
        $node->operands[] = $ch[0];
    } else if ($name == '*?') {
        $node = form_quant('*?', true, 0, -1, true, false, false);
        $node->operands[] = $ch[0];
    } else if (preg_match('/{([0-9]),([0-9])}(?)/', $name, $matches)) {
        $is = count($matches) == 4;
        $node = form_quant('', false, $matches[1], $matches[2], $is, !$is, false);
        $node->operands[] = $ch[0];
    } else if (preg_match('/{,([0-9])}(?)/', $name, $matches)) {
        $is = count($matches) == 3;
        $node = form_quant('', false, 0, $matches[1], $is, !$is, false);
        $node->operands[] = $ch[0];
    } else if (preg_match('/{([0-9]),}(?)/', $name, $matches)) {
        $is = count($matches) == 3;
        $node = form_quant('', true, $matches[1], -1, $is, !$is, false);
        $node->operands[] = $ch[0];
    } else if (preg_match('/{([0-9])}(?)/', $name, $matches)) {
        $is = count($matches) == 3;
        $node = form_quant('', false, $matches[1], $matches[1], $is, !$is, false);
        $node->operands[] = $ch[0];
    } else if (core_text::substr($name, 0, 3) == '(?(') {
        $node = new qtype_preg_node_cond_subexpr(qtype_preg_node_cond_subexpr::SUBTYPE_SUBEXPR, core_text::substr($name, 3, $name->length() - 12));
        $node->operands[] = $ch[0];
        $node->operands[] = $ch[1];
    } else {
        $node = form_charset($name->string(), qtype_preg_charset_flag::TYPE_SET, $name->string());
    }

    return $node;
}

function equal_trees($first, $second) {
    if ($first == null && $second == null) {
        return true;
    } else if ($first == null || $second == null) {
        return false;
    }

    if ($first->type != $second->type || $first->subtype != $second->subtype) {
        return false;
    }
    $equal = true;

    if ($first->type == qtype_preg_node::TYPE_LEAF_ASSERT && $first->negative != $second->negative) {
        $equal = false;
    } else if ($first->type == qtype_preg_node::TYPE_LEAF_CHARSET &&
            $first->flags[0][0]->data != $second->flags[0][0]->data) {
        $equal = false;
    } else if ($first->type == qtype_preg_node::TYPE_LEAF_SUBEXPR_CALL &&
            $first->number != $second->number) {
        $equal = false;
    } else if ($first->type == qtype_preg_node::TYPE_LEAF_BACKREF &&
            $first->number != $second->number) {
        $equal = false;
    } else if ($first->type == qtype_preg_node::TYPE_NODE_FINITE_QUANT &&
            ($first->leftborder != $second->leftborder ||
            $first->rightborder != $second->rightborder ||
            $first->lazy != $second->lazy || $first->greedy != $second->greedy ||
            $first->possessive != $second->possessive)) {
        $equal = equal_trees($first->operands[0], $second->operands[0]);
    } else if ($first->type == qtype_preg_node::TYPE_NODE_INFINITE_QUANT &&
            ($first->leftborder != $second->leftborder ||
            $first->lazy != $second->lazy || $first->greedy != $second->greedy ||
            $first->possessive != $second->possessive)) {
        $equal = equal_trees($first->operands[0], $second->operands[0]);
    } else if ($first->type == qtype_preg_node::TYPE_NODE_CONCAT ||
            $first->type == qtype_preg_node::TYPE_NODE_ALT) {
        $c1 = count($first->operands);
        $c2 = count($second->operands);
        if ($c1 != $c2) {
            $equal = false;
        } else {
            for ($i = 0; $i < $c1; $i++) {
                $equal = $equal && equal_trees($first->operands[$i], $second->operands[$i]);
            }
        }
    } else if ($first->type == qtype_preg_node::TYPE_NODE_SUBEXPR &&
            $first->subtype == qtype_preg_node_subexpr::SUBTYPE_SUBEXPR &&
            ($first->number != $second->number || $first->name != $second->name)) {
        $equal = equal_trees($first->operands[0], $second->operands[0]);
    } else if ($first->type == qtype_preg_node::TYPE_NODE_COND_SUBEXPR &&
            $first->number != $second->number) {
        $equal = equal_trees($first->operands[0], $second->operands[0]);
        $equal = $equal && equal_trees($first->operands[1], $second->operands[1]);
    }

    return $equal;
}

/**
 * Forms an interval from sequences like a-z, 0-9, etc. If a string contains
 * something like "x-z" in the end, it will be converted to "xyz".
 */
function expand_charset_range($charsetset) {
    $charsetcount = core_text::strlen($charsetset);
    // Check if there are enough characters in before.
    if ($charsetcount < 3 || qtype_preg_unicode::substr($charsetset, $charsetcount - 2, 1) != '-') {
        return $charsetset;
    }
    $startchar = qtype_preg_unicode::substr($charsetset, $charsetcount - 3, 1);
    $endchar = qtype_preg_unicode::substr($charsetset, $charsetcount - 1, 1);

    if (core_text::utf8ord($startchar) <= core_text::utf8ord($endchar)) {
        // Replace last 3 characters by all the characters between them.
        $charsetset = qtype_preg_unicode::substr($charsetset, 0, $charsetcount - 3);
        $charsetcount -= 3;
        $curord = core_text::utf8ord($startchar);
        $endord = core_text::utf8ord($endchar);
        while ($curord <= $endord) {
            $charsetset .= qtype_preg_unicode::code2utf8($curord++);
            $charsetcount++;
        }
    } else {
        // Delete last 3 characters.
        $charsetcount -= 3;
        $charsetset = qtype_preg_unicode::substr($charsetset, 0, $charsetcount);
        // Form the error node.
        $error = form_error(qtype_preg_node_error::SUBTYPE_INCORRECT_CHARSET_RANGE, $startchar . '-' . $endchar, $charsetset);
    }
    return $charsetset;
}